package com.cb2.algorithm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/sliding-window-maximum">滑动窗口最大值(Sliding Window Maximum)</a>
 * <p>给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。</p>
 * <p>返回 滑动窗口中的最大值 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 *      输出：[3,3,5,5,6,7]
 *      解释：
 *          滑动窗口的位置                最大值
 *          ---------------               -----
 *          [1  3  -1] -3  5  3  6  7       3
 *           1 [3  -1  -3] 5  3  6  7       3
 *           1  3 [-1  -3  5] 3  6  7       5
 *           1  3  -1 [-3  5  3] 6  7       5
 *           1  3  -1  -3 [5  3  6] 7       6
 *           1  3  -1  -3  5 [3  6  7]      7
 * 示例 2：
 *      输入：nums = [1], k = 1
 *      输出：[1]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 10^5</li>
 *     <li>-10^4 <= nums[i] <= 10^4</li>
 *     <li>1 <= k <= nums.length</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/8 9:57
 */
public class LC0239SlidingWindowMaximum_H {
    static class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            // 双端队列中元素保持单调递减，因为后面出现的大数会使前面的较小数无意义。
            // 但后面的较小数是有意义的，因为前面的大数会逐渐从窗口中移出，此时较小数可能会成为新的最大数
            Deque<Integer> d = new LinkedList<>();
            int[] ans = new int[nums.length - k + 1];
            for (int i = 0; i < nums.length; i++) {
                // 每添加一个元素，都会使队列中维护的比当前元素小的元素弹出
                // 这些元素和当前元素在同一个窗口内，是无意义的。
                while (!d.isEmpty() && d.peekLast() < nums[i]) {
                    d.removeLast();
                }
                d.addLast(nums[i]);
                // 当i >= k - 1 条件满足时，窗口形成，元素为k个，可得到一个最大值
                if (i >= k - 1) {
                    // 更新返回值。双端队列中元素不会为null，这里做健壮性校验
                    Integer currMaxVal = d.peekFirst();
                    if (currMaxVal != null) {
                        ans[i - k + 1] = currMaxVal;
                        // 如果这个最大值，恰好是窗口的最左侧元素，在下一次窗口移动时，则需要从窗口中移出
                        if (currMaxVal == nums[i - k + 1]) {
                            d.removeFirst();
                        }
                    }
                }
            }
            return ans;
        }

        public int[] maxSlidingWindow2(int[] nums, int k) {
            // 双端队列中元素保持单调递减，因为后面出现的大数会使前面的较小数无意义。
            // 但后面的较小数是有意义的，因为前面的大数会逐渐从窗口中移出，此时较小数可能会成为新的最大数
            Deque<Integer> d = new LinkedList<>();
            // 窗口未形成时，窗口内包含k-1个元素
            for (int i = 0; i < k - 1; i++) {
                while (!d.isEmpty() && d.peekLast() < nums[i]) {
                    d.removeLast();
                }
                d.addLast(nums[i]);
            }
            // 此时窗口形成，元素为k个
            int[] ans = new int[nums.length - k + 1];
            for (int i = k - 1; i < nums.length; i++) {
                while (!d.isEmpty() && d.peekLast() < nums[i]) {
                    d.removeLast();
                }
                d.addLast(nums[i]);
                // 窗口形成，可得到一个最大值
                Integer currMaxValue = d.peekFirst();
                if (currMaxValue != null) {
                    ans[i - k + 1] = currMaxValue;
                    // 如果这个最大值，恰好是窗口的最左侧元素，则需要从窗口中移出。
                    // 因为在下一次窗口移动时，将不在窗口范围内
                    if (currMaxValue == nums[i - k + 1]) {
                        d.removeFirst();
                    }
                }
            }
            return ans;
        }
    }
}
